# !/usr/bin/env python
# -*- coding: utf-8 -*-

#  Reference: https://blog.csdn.net/weizhifei1234/article/details/88787352
#  Usage: Implement DFS with python.

# --------- 定义一个图结构 --------- #
graph = {
        'A': ['B','C'],
        'B': ['A','C','D'],
        'C': ['A','B','D','E'],
        'D': ['B','C','E','F'],
        'E': ['C','D'],
        'F': ['D']
        }

def DFS(graph,s): # s指的是开始结点
    stack=[] # 定义一个队列
    stack.append(s)
    seen = set() # 看是否访问过
    seen.add(s)
    while len(stack) > 0:
        vertex = stack.pop()
        nodes = graph[vertex] # 拿出邻接点
        for w in nodes:
            if w not in seen: # 如何判断是否访问过，使用一个数组
                stack.append(w)
                seen.add(w)
        print(vertex)

DFS(graph,'A')